#include <iostream>
#include <limits.h>
#include <string.h>
int coinChange(int [], int, int);
int coinChange(int coins[], int len, int target)
{
    //dp table解法
    int dp[target + 1];
    memset(dp, target + 1, sizeof(dp));  //注意每个值都被初始化为target + 1,而不是 target
    //凑出targte的金额的硬币最多只需要为target（全部使用1元硬币），而设置为target+1可以视为无穷；
    dp[0] = 0;
    for(int i = 1; i <= target; i++)
    {
        for(int j = 0; j < len; j++)
        {
            if (i - coins[j] < 0) continue;
            dp[i] = dp[i - coins[j]] + 1 < dp[i] ? dp[i - coins[j]] + 1 : dp[i];
            //计算值 dp[i - coins[j]] + 1 和 自己比较，更新为较小值
        }
    }
    return dp[target] == target + 1 ? -1 : dp[target];
}
/*
dp[0] [1] [2] [3] [4] [5]
  0   1   11  11  11  11

*/

int main()
{   
    using namespace std;
    int coins[3] = {1, 2, 5};
    int target = 11;
    int memo[target + 1];
    memset(memo, 0, sizeof(memo));
    cout << coinChange(coins, 3, target) << endl;
    return 0;
}